#include"HashTable.h"
#include<stdlib.h>
#include<stdbool.h>
#include<math.h>
#include<string.h>
typedef unsigned int Index;
static inline int expand_hash(Hash_Table *ht);
/*---------哈希函数-------------*/

// 此哈希函数作废
//  Index hashFun(const Hash_Table *ht,const char *key, const char *value)
//  {
//      size_t len = strlen(key);
//      if(len>16)
//      {
//          return key[0] + key[1] * 27 + key[2] * 27 * 27;
//      }
//      else
//      {
//          size_t hashval = 0;
//          while(*key!='\0')
//          {
//              hashval = (hashval << 5) + *key++;
//          }
//          return hashval%ht->tableSize;
//      }
//  }

// yyds
/**
 * djb2哈希函数由计算机科学家Daniel J. Bernstein设计，是一个简* 单且有效的哈希函数。其主要特性是易于实现和较好的分布均匀性。
 */
static Index hashFun(struct Hash_Table *ht, const char *key, const char *value)
{
    unsigned long long hash = 5381;
    int c;
    while ((c = *key++))
    {
        hash = ((hash << 5) + hash) + c; // hash * 33 + c
    }
    return hash % ht->tableSize;
}
/*----------------------一堆内联函数--------------------*/
/**
 * 销毁键值对
 */
static inline int del_pair(Pair **p)
{
    if (NULL == p)
        return 1;
    free((*p)->key);
    free((*p)->value);
    (*p)->key = NULL;
    (*p)->value = NULL;
    free(*p);
    *p = NULL;
    return 0;
}
/**
 * 检查内存是否分配成功
 */
static inline int check_Memory(void *p)
{
    if (NULL == p) {
        fprintf(stderr,"malloc error\n");
        return 1;
    }
    return 0;
}
/**
 * 判断number是否是素数
 * @param number---待判断的数
 */
static inline bool is_prime(int number)
{
    //该函数使用前提:参数必定大于DEFAUL_TableSize---这里是31.
    if (number % 2 == 0 || number % 3 == 0)
        return false; // 2 和 3 的倍数不是质数

    // 从 5 开始检查到 sqrt(number)
    int target = (int)floor(sqrt(number));
    for (int i = 5; i<= target; i += 6)
    {
        if (number % i == 0 || number % (i + 2) == 0)
            return false;
    }

    return true;
}
/**
 * @return
 * 返回大于等于number的最小质数
 */
static inline int next_prime(int number)
{
    //number>31,且其不为3的倍数.
    while(!is_prime(number))
        number += 2;
    return number;
}
/**
 * 调整初始化给定参数的大小,以确保它是素数,且至少 >=DEFAULT_TableSize
 */
static inline int AdjustSize(Hash_Table *ht,int *size)
{
    int newSize = *size;
    //不足则调整为默认值
    if (newSize < DEFAULT_TableSize)
        *size = DEFAULT_TableSize;
    //如果大于默认值,则检查是否是素数
    if(is_prime(newSize))
    {
        *size = newSize;
        return 0;
    }
    else//不为素数,则调整为大于等于newSize的最小素数
    {
        *size = next_prime(newSize);
        return 0;
    }
}
/*-----------------------接口函数的具体实现-------------*/
/**
 * @brief 根据给定参数(字符串)创建一对键值对
 * @param key-键 
 * @param value-值
 * @return 返回创建的键值对
 * static修饰,该函数接口只供内部使用---封装性
 */
static Pair *newPair(const char *key, const char *value)
{
    Pair *p = (Pair *)malloc(sizeof(Pair));
    check_Memory(p);
    size_t len_k = strlen(key) + 1;
    char *k = (char *)malloc(sizeof(char) * len_k);
    if(check_Memory((void *)k)) 
        return NULL;
    size_t len_v = strlen(value) + 1;
    char *v = (char *)malloc(sizeof(char) * len_v);
    if(check_Memory((void*)v))
        return NULL;
    memcpy(k, key, len_k);
    memcpy(v, value, len_v);
    p->key = k;
    p->value = v;
    return p;
}
/**
 * @brief 初始化哈希表----此法主要针对结构体变量使用.
 * @param ht-哈希表--->结构体变量取地址
 * @param size-哈希表大小
 * @return 返回0,表示初始化成功;返回1,意味着传入空地址或者内存申请失败.
 */
int HashInit(Hash_Table *ht,int size)
{
    if(ht==NULL)
        return 1;
    AdjustSize(ht,&size);
    ht->buckets = (Pair **)malloc(sizeof(Pair *) * size);
    if (check_Memory((void *)ht->buckets))
    {
        return 1;
    }
    // 初始化字段
    ht->count = 0;
    ht->tableSize = size;
    for (int i = 0; i < ht->tableSize; i++)
        ht->buckets[i] = NULL;
    // 初始化方法指针
    ht->isEmpty = isEmpty_hash;
    ht->print = print_hash;
    ht->getfactor = get_load_factor;
    ht->destroy = del_hash_table;
    ht->put = insert_hash;
    ht->search = search_hash;
    ht->remove = delete_hash;
    ht->getVal = get_one_value;
    ht->setVal = set_one_value;
    ht->getAllKey = get_all_key;
    ht->getAllVal = get_all_value;
    ht->getAllPair = get_all_pair;
    return 0;
}
/**
 * @brief 初始化哈希表----此法主要针对结构体指针使用.
 * @param size-哈希表大小
 * @return 返回哈希表指针,如果初始化失败,则返回NULL
 */
Hash_Table *newHash_Table(int size){
    Hash_Table *ht = (Hash_Table *)malloc(sizeof(Hash_Table));
    if(check_Memory((void*)ht))
        return NULL;
    AdjustSize(ht,&size);
    ht->buckets = (Pair **)malloc(sizeof(Pair *) * size);
    if(check_Memory((void*)ht->buckets))
    {
        free(ht);
        //写个错误信息提醒一下.
        fprintf(stderr, "newHash_Table:malloc buckets failed!\n");
        return NULL;
    }
    //初始化字段
    ht->count = 0;
    ht->tableSize = size;
    for (int i = 0; i < ht->tableSize;i++)
        ht->buckets[i] = NULL;
    //初始化方法指针
    ht->isEmpty = isEmpty_hash;
    ht->print = print_hash;
    ht->getfactor = get_load_factor;
    ht->destroy = del_hash_table;
    ht->put = insert_hash;
    ht->search = search_hash;
    ht->remove = delete_hash;
    ht->getVal = get_one_value;
    ht->setVal = set_one_value;
    ht->getAllKey = get_all_key;
    ht->getAllVal = get_all_value;
    ht->getAllPair = get_all_pair;
    return ht;
}
/**
 * @brief 释放哈希表中所有键值对,并释放哈希表本身
 * @param ht-哈希表指针(地址)
 * @return 返回0,表示释放成功;返回1,表示传入空地址或者键值对释放失败.
 */
int del_hash_table(Hash_Table *ht)
{
    if(ht==NULL)
        return 1;
    for (int i = 0; i < ht->tableSize;i++)
    {
        if(ht->buckets[i]){
            if(del_pair(ht->buckets + i))
                return 1;
            free(ht->buckets[i]);
            ht->buckets[i] = NULL;
        }
    }
    free(ht->buckets);
    // 若外部是结构体指针,且调用newHash_Table()申请的,则其在堆上需要在外部free.----free(ht)并置空处理.
    // 若是结构体本身传地址,则只需置空处理.
    return 0;
}

//哈希表基本操作
//插入操作
/**
 * @brief 插入键值对
 * @param ht---哈希表指针(地址)
 * @param key---键
 * @param value---值
 */
int insert_hash(Hash_Table *ht, const char *key, const char *value){
    if(NULL==ht||NULL==key||NULL==value)
        return 1;
    Index index = hashFun(ht, key, value);
    Pair *p = newPair(key, value);
    // 哈希冲突处理---该版本未解决哈希冲突-而是允许值被覆盖.
    if(ht->buckets[index])
    {
        //发生哈希冲突,值被覆盖,已填入哈希表有效数据不增加.
        ht->buckets[index] = p;
        return 0;
    }
    ht->buckets[index] = p;
    ht->count++;
    if(expand_hash(ht))
        return 1;
    return 0;
}
/**
 * @brief 删除键值对---对应内置方法的remove操作.
 * @param ht---哈希表指针(地址)
 * @param key---键
 * @return 返回0,表示删除成功;返回1,表示传入空地址或者键值对不存在.
 */
int delete_hash(Hash_Table *ht, const char *key){
    if (NULL == ht||NULL == key)
        return 1;
    Index index = hashFun(ht, key, NULL);
    if(!ht->buckets[index])
        return 1;
    else{
        free(ht->buckets[index]);
        ht->buckets[index] = NULL;
        ht->count--;
    }
    return 0;
}
/**
 * 根据key关键词--查找对应的value值.
 * @brief 查找键值对---对应内置方法的search操作.
 * @param ht---哈希表指针(地址)
 * @param key---键
 * @param resultVal---用于接受实际的返回值value,如果查找失败则                     (*resultVal)保持不变.
 * @return 返回0,表示查找成功;返回1,表示传入空地址或者键值对不存在.
 * 传参说明:
 *  Hash_Table ht;
    HashInit(&ht, 19);
    ht.put(&ht, "1", "a");
    char *resulVal = NULL;//必须这样处理
    ht.search(&ht, "1", &resulVal);
    若search方法执行成功,则resulVal指向的内存地址为"a",否则resulVal仍然为NULL.这是最安全的做法.
 */
int search_hash(Hash_Table *ht,const char *key, char **resultVal){
        if(NULL == ht||NULL == key)
            return 1;
        Index index = hashFun(ht, key, NULL);
        if(NULL == ht->buckets[index])
            return 1;
        else
        {
            size_t len = strlen(ht->buckets[index]->value)+1;
            char *tmp = (char *)malloc(sizeof(char) * len);
            if(check_Memory((void*)tmp))
                return 2;
            memcpy(tmp, ht->buckets[index]->value, len);
            *resultVal = tmp;
            return 0;
        }
}
/**
 * @brief 获取所有的键
 */
int get_all_key(Hash_Table *ht, char ***resultKey,size_t *returnSize){
    if (!ht)
        return 1;
    if (!resultKey)
        return 1;
    *resultKey = (char **)realloc(*resultKey, sizeof(char *) * ht->count);
    if (check_Memory((void *)*resultKey))
        return 1;
    int j = 0;
    for (int i = 0;i<ht->tableSize;i++)
    {
        if(NULL != ht->buckets[i])
        {
            size_t len = strlen(ht->buckets[i]->key)+1;
            (*resultKey)[j] = (char *)malloc(sizeof(char) *len);
            memcpy((void*)(*resultKey)[j], (void*)ht->buckets[i]->key,len - 1);
            (*resultKey)[j++][len - 1] = '\0';
        }
    }
    *returnSize = j;
    return 0;
}
//获取某个key对应的value
int get_one_value(Hash_Table *ht, const char *key,char **resultVal)
{
    if(NULL == ht)
        return 1;
    Index index = hashFun(ht, key, NULL);
    if(ht->buckets[index]==NULL)
        return 1;
    size_t len = strlen(ht->buckets[index]->value)+1;
    char *value = (char *)malloc(sizeof(char) * len);
    if(check_Memory(value))
        return 1;
    memcpy(value, ht->buckets[index]->value, len);
    *resultVal = value;
    return 0;
}
//设置单个键对应的值
int set_one_value(Hash_Table *ht, const char *key,const char*setValue)
{
    if (NULL == ht)
        return 1;
    Index index = hashFun(ht, key, NULL);
    if (ht->buckets[index] == NULL)
        return 1;
    size_t len = strlen(setValue) + 1;
    char *tmp = ht->buckets[index]->value;
    tmp = (char *)realloc((void *)tmp, len);
    if (check_Memory(tmp))
        return 1;
    memcpy(ht->buckets[index]->value, setValue, len-1);
    ht->buckets[index]->value[len - 1] = '\0';
    return 0;
}
/**
 * @brief 获取所有的value值
 * @param ht---哈希表指针(地址)
 * @param resultValue---用于接受实际的返回值value,如果查找失败则                     (*resultVal)保持不变.
 * @param returnSize---返回value的个数---接受数组的大小,如果查找失败则                     (*returnSize)保持不变.
 */
int get_all_value(Hash_Table *ht, char ***resultValue,size_t *returnSize){
    if (NULL == ht)
        return 1;
    if (resultValue == NULL)
        return 1;
    *resultValue = (char **)realloc(*resultValue, sizeof(char *) * ht->count);
    if(check_Memory((void*)*resultValue))
        return 1;
    int j = 0;
    for (int i = 0;i<ht->tableSize;i++)
    {
        if(NULL != ht->buckets[i])
        {
            size_t len = strlen(ht->buckets[i]->value)+1;
            (*resultValue)[j] = (char *)malloc(sizeof(char) *len);
            memcpy((void*)(*resultValue)[j], (void*)ht->buckets[i]->value,len - 1);
            (*resultValue)[j++][len - 1] = '\0';
        }
    }
    *returnSize = j;
    return 0;
}
//获取键值对
int get_all_pair(Hash_Table *ht, Pair ***resultPair,size_t *returnSize){
    if (NULL == ht)
        return 1;
    if(resultPair == NULL)
        return 1;
    *resultPair = (Pair **)realloc(*resultPair, sizeof(Pair *) * ht->count);
    if(check_Memory((void*)*resultPair))
        return 1;
    int j = 0;
    for (int i = 0;i<ht->tableSize;i++)
    {
        if(NULL != ht->buckets[i]){
            (*resultPair)[j] = (Pair *)malloc(sizeof(Pair));
            memcpy((void*)(*resultPair)[j], (void*)ht->buckets[i],sizeof(Pair));
            j++;
        }
    }
    *returnSize = j;
    return 0;
}

/*----------补充一些简单方法-------------*/
bool isEmpty_hash(Hash_Table *ht)
{
    ht->count==0?true:false;
}

int get_load_factor(Hash_Table *ht,double *resultFactor)
{
     *resultFactor = (double)ht->count / ht->tableSize;
     return 0;
}

/*--------------哈希扩充---------------------*/

static inline int expand_hash(Hash_Table *ht)
{
    if ((double)ht->count / ht->tableSize>DEFAULT_LOADFACTOR)
    {
        Pair **tmp = (Pair**)malloc(sizeof(Pair*) * ht->tableSize*2);
        if(check_Memory((void*)tmp))
            return 1;//内存申请失败
        for (int i = 0;i<ht->tableSize;i++)
        {
            if(NULL==ht->buckets[i])
                continue;
            else{
            Index index = hashFun(ht, ht->buckets[i]->key, NULL);
            tmp[index] = ht->buckets[i];
            free(ht->buckets[i]);
            }
        }
        free(ht->buckets);
        ht->buckets = tmp;
        return 0;//扩容完毕
    }
    else
    {
        return 0; // 不需要扩容正常返回;
    }
}

int print_hash(Hash_Table *ht)
{
    if (NULL == ht)
        return 1;
    printf("[");
    for (int i = 0;i<ht->tableSize;i++)
    {
        if(NULL == ht->buckets[i])
            continue;
        printf("\"%s=%s\",",ht->buckets[i]->key,ht->buckets[i]->value);
        
    }
    printf("end]\n");
    return 0;
}